#pragma once

#include <iostream>
#include <vector>
#include <string>
using namespace std;

vector<int> st_hour = { 1,2,4,8 };
vector<int> st_second = { 1,2,4,8,16,32 };
class Solution {
public:
    void dfs(vector<int>& num, int count, int start, int sum, vector<int>& ret)
    {
        if (count == 0)
        {
            ret.push_back(sum);
            return;
        }
        for (int i = start; i < num.size(); ++i)
        {
            dfs(num, count - 1, i + 1, sum + num[i], ret);
        }
    }
    vector<int> findCom(vector<int>& num, int count)
    {
        vector<int> ret;
        dfs(num, count, 0, 0, ret);
        return ret;
    }
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (int i = 0; i <= turnedOn; ++i)
        {
            vector<int> hour = findCom(st_hour, i);
            vector<int> minute = findCom(st_second, turnedOn - i);

            for (auto& e1 : hour)
            {
                if (e1 > 11) continue;
                string str1 = to_string(e1);
                str1 += ':';
                for (auto& e2 : minute)
                {
                    if (e2 > 59) continue;
                    string str2 = (e2 < 10) ? "0" + to_string(e2) : to_string(e2);
                    ans.push_back(str1 + str2);
                }
            }
        }
        return ans;
    }
};
